##include<stdio.h>
#include<stdlib.h>

struct node{
int num;
struct node *next;
};

struct node *first=NULL;
struct node *start=NULL;
struct node *s=NULL;
struct node *ex=NULL;


struct node *add_list(struct node *list , int n)
{struct node *new_node;
new_node=malloc(sizeof(struct node));
if(new_node==NULL)
{
printf("memory not allocated");
 }
new_node->num=n;
new_node->next=list;
return new_node;
}


struct node *create(int n)
{
int i=0;
for(; ;)
{i++;
printf("element(0 to terminate):");
scanf("%d",&n);
if(n==0)
break;
first = add_list(first,n);
}
}

struct node *print(struct node *p)
{
for(p=first;p!=NULL;p=p->next)
{
first = add_list(first,p->num);
printf("%d-->",p->num);
}
}

struct node *orig_list(int m)
{struct node *new_node1;
new_node1=malloc(sizeof(struct node));
if(new_node1==NULL)
{
printf("memory not allocated");
 }
new_node1->num=m;
new_node1->next=start;
return new_node1;
}


struct node *read2()
{struct node *p;
for(p=first;p!=NULL;p=p->next)
start = orig_list(p->num);
}


struct node *print_orig(struct node *p,struct node *start)
{
printf("\n");
for(p=start;p!=NULL;p=p->next)
printf("%d-->",p->num);
}


struct node *reverse(int m)
{struct node *new_node1;
new_node1=malloc(sizeof(struct node));
if(new_node1==NULL)
{
printf("memory not allocated");
 }
new_node1->num=m;
new_node1->next=s;
return new_node1;
}



struct node *readrev()
{struct node *p;
for(p=start;p!=NULL;p=p->next)
{
s= reverse(p->num);
}
}


void append(int val,struct node *p)
{
struct node *new_node;
new_node=malloc(sizeof(struct node));
printf("\nenter number to be appended:");
scanf("%d",&val);
for(p=start;p!=NULL;p=p->next)
 { if(p->next==NULL)
   { new_node->num=val;
     new_node->next=NULL;
     p->next=new_node;
     break;
    }
  }
print_orig(p,start);
}



struct node *insert(struct node *p)
{int j=0,n,pos,val,flag=0;
struct node *new,*l1;
new=malloc(sizeof(struct node));
printf("enter position:");
scanf("%d",&pos);
printf("\nenter number:");
scanf("%d",&val);
l1=p;
 if(pos==0)
  {new->num=val;
   new->next=l1;
   return new;
   flag=1;}
 else
 {for(;;l1=l1->next)
 {if(j==(pos-1))
  {new->num=val;
   new->next=l1->next;
   l1->next=new;flag=1;
   break;
  }j++;}
  if(flag==0)
  {printf("index position doesn't exist \n");}
   }
print_orig(p,start);
}



void count(int a)
{
struct node *p;
int i=0;
for(p=start;p!=NULL;p=p->next)
{
if(p->num==a)
i++;
else if(p->next==NULL)
printf("0");
}
printf("Number of occurrences of %d is %d",a,i);
}



struct node *remove_list(struct node *p, int n)
{
  struct node *cur, *prev;
  for (cur = start, prev = NULL;
       cur != NULL && cur->num != n;
       prev = cur, cur = cur->next);
  if (cur == NULL) 
	{printf("number not found\n");    
	return p;}             /* n was not found */
  if (prev == NULL)
    p = p->next;       /* n is in the first node */
  else
    prev->next = cur->next;  /* n is in some other node */
    
  return p;
} 




struct node *pop(struct node *p, int n)
{
  struct node *cur, *prev;
  for (cur = start, prev = NULL;
       cur != NULL && cur->num != n;
       prev = cur, cur = cur->next);
  if (cur == NULL) 
	{printf("number not found\n");    
	return p;}             /* n was not found */
  if (prev == NULL)
    p = p->next;       /* n is in the first node */
  else
    prev->next = cur->next;  /* n is in some other node */
  printf("\npopped number is %d:", cur->num);
  
  return p;
} 



void index(int m)
{
struct node *p;
int n,i=0,j=0;
for(p=start;p!=NULL;p=p->next)
{
i++;
}
n=i;
for(p=start;p!=NULL;p=p->next)
{
j++;
if(p->num==m)
{printf("\nindex:%d",j-1);
break;}
else if(n<=j)
{printf("number not found");
break;
}
}
}



void extend()
{int n;
struct node *tmp;
create(n);
read2();
}




void sort()
{
   struct node *p,*second,*temp,*new;
    
    while(p!=NULL){
    second=p->next;
         while(second!=NULL){
            if(p->num < second->num){
                temp = new->num;
                temp->num=p->num;
                p->num=second->num;
                second->num=temp->num;
                free(temp);
            }
 
        second=second->next;
        }
 
    p=p->next;
    }

}


void main()
{
int n,val,op;
int *list,*p,*tmp;
printf("\t List data structure \t\n Functions are \n1.append\n2.remove\n3.pop\n4.index\n5.extend\n6.count\n7.sort\n8.reverse\n9.insert\nn10.exit\n11.display\n12.menu\nenter:");
printf("create initial list\n");
add_list(list,n);
create(n);
orig_list(n);
read2();
printf("entered list: \n");
print_orig(p,start);

while(op!=10)
{
printf("\nenter function number:");
scanf("%d",&op);

switch(op)
{
case 1:append(val,p);break;


case 2:printf("enter number to remove");
	scanf("%d",&val);
	remove_list(p,val);
	print_orig(p,start);break;


case 3 :printf("enter number to pop");
	scanf("%d",&val);
	pop(p,val);
	print_orig(p,start);break;


case 4:printf("enter number to find index");
	scanf("%d",&val);
	index(val);break;


case 5: extend();
	print_orig(p,start);
	break;


case 6:printf("enter number to count");
	scanf("%d",&val);
  count(val);


case 7 :sort();
	print_orig(p,s);


case 8:reverse(n);
	readrev();
	print_orig(p,s);	
	break;


case 9:insert(p);break;


case 10:break;


case 11: print_orig(p,start);break;


case 12:printf("\t List data structure \t\n Functions are \n1.append\n2.remove\n3.pop\n4.index\n5.extend\n6.count\n7.sort\n8.reverse\n9.insert\nn10.exit\n11.display\n12.menu\nenter:");break;


default:printf("wrong choice\n");
}
}
}


